package com.kitty.record.kittyalgorithm.audition;


/**
 * 给定一个有序整数数组，元素各不相同且按升序排列，
 * 编写一个算法，创建一棵高度最小的二叉搜索树。
 * 示例:
 * 给定有序数组: [-10,-3,0,5,9],
 * 一个可能的答案是：[0,-3,9,-10,null,5]，
 * 它可以表示下面这个高度平衡二叉搜索树：
 *      0
 *     / \
 *    -3  9
 *   /   /
 * -10  5
 * @Author SHEN
 * @Date 2020/12/18
 */
public class LeetCode0402 {

    public TreeNode sortedArrayToBST(int[] nums) {

        return build(nums,0,nums.length-1);
    }

    public TreeNode build(int[] nums,int low,int heigh){
        if(low > heigh){
            return null;
        }
        //获取根节点的index
        int mid = (heigh+low)/2;
        TreeNode treeNode = new TreeNode(nums[mid]);
        //使用递归构建左子树
        treeNode.left = build(nums,low,mid-1);
        //使用递归构建右子树
        treeNode.right = build(nums,mid+1,heigh);
        return treeNode;
    }

    private class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode(int x) {
            this.val = x;
        }
    }
}



